We study the impact of a strongly first-order electro-weak phase transition on the thermal relic abundance of particle species that could constitute the dark matter and that decoupled before the phase transition occurred. We define a dilution factor induced by generic first-order phase transitions, and we explore the parameter space of the minimal supersymmetric extension to the Standard Model to determine which phase transition temperatures and dilution factors are relevant for the lightest neutralino as a dark matter candidate. We then focus on a specific toy-model setup that could give rise to a strongly first-order electro-weak phase transition, and proceed to a detailed calculation of dilution factors and transition temperatures, comparing our findings to actual neutralino dark matter models. Typical models that would produce an excessive thermal relic density and that can be salvaged postulating a strongly first-order electro-weak phase transition include massive (multi-TeV) wino or higgsino-like neutralinos, as well as bino-like neutralinos in a wider mass range, with masses as low as 400 GeV. If LHC data indicate an inferred thermal neutralino relic abundance larger than the cold dark matter density, the mismatch could thus potentially be explained by electro-weak scale physics that will also be thoroughly explored with collider experiments in the near future.